25C - Roads in Berland - CodeForces Solution

// Author : Mr_Sa3dola
#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define all(x)  (x).begin() , (x).end()
#define allr(u) (u).rbegin(), (u).rend()
#define F first
#define S second
#define sz(a) (int)(a).size()

const int N = 2e5 + 5, M = 120, MOD = 1e9 + 7, OO = 1e18 + 7;

int dx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
int dy[] = {+1, -1, +0, +0, +1, -1, -1, +1};

void solution(int cas) {
    int n;
    cin >> n;
    vector<vi> dist(n + 1, vi(n + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> dist[i + 1][j + 1];
        }
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int u, v, w;
        cin >> u >> v >> w;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min({dist[i][j], dist[i][u] + dist[v][j] + w, dist[i][v] + dist[u][j] + w});
                ans += dist[i][j];
            }
        }
        cout << ans / 2 << ' ';
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(18);
    int tc = 1, cas = 1;
    while (tc--) {
        solution(cas++);
    }
    return 0;
}